package com.yaoxiaoqing.objectclass;

/*
 * 递归方法的使用(了解)
 * 1.递归方法：一个方法体内调用它自身。
 * 2.方法递归包含了一种隐式的循环，它会重复执行某段代码，但这种重复执行无须循环控制。
 *
 * 3.递归一定要向已知方向递归，否则这种递归就变成了无穷递归，类似于死循环。
 *
 */
public class Recursion {
    public static void main(String[] args) {
        Recursion test = new Recursion();

        System.out.println("普通" + test.getSum1(100));//5050

        System.out.println("递归" + test.getSum(100));//5050

        System.out.println("递归阶乘" + test.getSum2(4));//24

        System.out.println("求和1" + test.getSum3(10));//10497
        //报错：栈溢出，递归没运行到退出条件
        //System.out.println("求和2" + test.getSum4(10));//
        System.out.println("斐波那契数列" + test.getSum5(10));//55


    }

    //1.普通遍历求1-n的和
    public int getSum1(int n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += i;
        }
        return sum;
    }

    //2.递归计算1-n之间所有自然数的和
    public int getSum(int n) {
        if (n == 1) {
            return 1;
        } else {
            return n + getSum(n - 1);
        }
    }

    //3.递归计算1-n之间的乘积
    public int getSum2(int n) {
        if (n == 1) {
            return 1;
        } else {
            return getSum2(n - 1) * n;
        }
    }

    //4.已知有一个数列：f(0) = 1,f(1) = 4,f(n+2)=2*f(n+1) + f(n),其中n是大于0的整数，求f(10)的值。
    public int getSum3(int n) {
        if (n == 0) {
            return 1;
        } else if (n == 1) {
            return 4;
        } else {
            return 2 * getSum3(n - 1) + getSum3(n - 2);
        }
    }

    //5.已知一个数列：f(20) = 1,f(21) = 4,f(n+2) = 2*f(n+1)+f(n),其中n是大于0的整数，求f(10)的值。
//    public int getSum4(int n) {
//        if(n==20){
//            return 1;
//        }else if(n==21){
//            return 4;
//        }else{
//            return 2 * getSum4(n - 1) + getSum4(n - 2);
//        }
//    }

    /*
     * 6.输入一个数据n，计算斐波那契数列(Fibonacci)的第n个值
     * 1  1  2  3  5  8  13  21  34  55
     * 规律：一个数等于前两个数之和
     * 要求：计算斐波那契数列(Fibonacci)的第n个值，并将整个数列打印出来
     *
     */
    public int getSum5(int n) {
        if(n==1||n==2){
            return 1;
        }else{
            return getSum5(n - 1) + getSum5(n - 2);
        }
    }
}
